package middle;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 给定一个经过编码的字符串，返回它解码后的字符串。
 *
 * 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
 *
 * 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
 *
 * 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像3a或2[4]的输入。
 *
 * 链接：https://leetcode-cn.com/problems/decode-string
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class DecodeString {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.decodeString("3[z]2[2[y]pq4[2[jk]e1[f]]]ef");
    }
    static class Solution {
        public String decodeString(String s) {
            Deque<String> stack = new LinkedList<>();
            StringBuilder result = new StringBuilder();
            for (char c : s.toCharArray()){
                if(c == ']'){
                    StringBuilder sb = new StringBuilder();
                    // 构建字符串
                    while(!stack.isEmpty() && !isNum(stack.peek()) && !isLeftBrackets(stack.peek())){
                        sb.append(stack.pop());
                    }
                    // 把左括号弹出去
                    if(!stack.isEmpty() && isLeftBrackets(stack.peek())){stack.pop();}

                    // 构建循环次数
                    StringBuilder countStr = new StringBuilder();
                    while (!stack.isEmpty() && !isLeftBrackets(stack.peek()) && isNum(stack.peek())){
                        countStr.append(stack.pop());
                    }
                    // 把左括号弹出去
                    if(!stack.isEmpty() && isLeftBrackets(stack.peek())){stack.pop();}
                    int count = Integer.parseInt(countStr.reverse().toString());

                    // 将循环后的字符串放入到栈 比如是2只需要循环一次（因为字符串本身算一次）
                    String tStr = sb.toString();
                    while(--count != 0){
                        sb.append(tStr);
                    }
                    stack.push(sb.toString());
                }
                else {
                    stack.push(String.valueOf(c));
                }

            }
            while(!stack.isEmpty()){
                result.append(stack.pop());
            }
            return result.reverse().toString();
        }

        boolean isNum(String s){
            return s.length() == 1 && s.charAt(0) >= '0' && s.charAt(0) <= '9';
        }

        boolean isLeftBrackets(String s){
            return s.length() == 1 && s.charAt(0) == '[';
        }
    }
}
